export default class HashTable {
  constructor(limit) {
    this.storage = [];
    this.count = 0;
    this.limit = limit;
  }
  // 哈希函数
  hashFunc(str, size) {
    let hashCode = 0;
    for (let i = 0; i < str.length; i++) {
      hashCode = 37 * hashCode + str.charCodeAt(i);
    }
    let index = hashCode % size;
    return index;
  }
  // 插入修改
  put(key, value) {
    let index = this.hashFunc(key, this.limit),
      bucket = this.storage[index];
    if (bucket == null) {
      bucket = [];
      this.storage[index] = bucket;
    }
    // 修改
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if (tuple[0] === key) {
        tuple[1] = value;
        return;
      }
    }
    // 添加
    bucket.push([key, value]);
    this.count += 1;
    // 判断是否需要扩容
    if (this.count >= this.limit * 0.75) {
      console.log(this.count);
      this.reSize(this.limit * 2);
    }
  }
  // 获取
  get(key) {
    let index = this.hashFunc(key, this.limit),
      bucket = this.storage[index];
    if (bucket == null) {
      return null;
    }
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if (tuple[0] === key) {
        return tuple[1];
      }
    }
    return null;
  }
  // 删除
  remove(key) {
    let index = this.hashFunc(key, this.limit),
      bucket = this.storage[index];
    if (bucket == null) {
      return null;
    }
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if (tuple[0] === key) {
        bucket.splice(i, 1);
        this.count--;
        if (this.count <= this.limit * 0.25) {
          this.reSize(Math.floor(this.limit / 2));
        }
        return tuple[1];
      }
    }
    return null;
  }
  isEmpty() {
    return this.count === 0;
  }
  size() {
    return this.count;
  }
  // 扩容
  reSize(newLimit) {
    let oldStorage = this.storage;
    this.storage = [];
    this.count = 0;
    this.limit = HashTable.getPrime(newLimit);
    for (let i = 0; i < oldStorage.length; i++) {
      let bucket = oldStorage[i];
      if (bucket == null) {
        continue;
      }
      for (let j = 0; j < bucket.length; j++) {
        let tuple = bucket[j];
        this.put(tuple[0], tuple[1]);
      }
    }
  }
  // 判断是否为质数
  static isPrime(num) {
    let temp = parseInt(Math.sqrt(num));
    for (let i = 2; i <= temp; i++) {
      if (num % i == 0) return false;
    }
    return true;
  }
  static getPrime(num) {
    while (!HashTable.isPrime(num)) {
      num += 1;
    }
    console.log(num);
    return num;
  }
}
